package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.bean.LinkNode;
import org.junit.Test;

/**
 * @author 60906
 * @date 2021/5/5 15:01
 */
public class Q_排序链表 {

    @Test
    public void foo() {
        int[] input = new int[]{4, 2, 1, 3};
        Solution solution = new Solution();
        LinkNode res = solution.sortList(LinkNode.toListNode(input));
        res.print();
        LinkNode res2 = new Solution_LC_1().sortList(LinkNode.toListNode(input));
        res2.print();
    }

    /**
     * 方法一：自顶向下归并排序
     *
     * 相比我,
     * 1) 利用 tailFlag . mid 用作左子链的 tailFlag, 作为右子链的 head, 右子链的 tailFlag 传入.
     * 2) 在此基础上, mid 取法就简单了. 没到 tailFlag 就移动.
     */
    class Solution_LC_1 {

        public LinkNode sortList(LinkNode head) {
            if (head == null) {
                return null;
            }

            return func(head, null);
        }

        /**
         *
         * @param head
         * @param tailFlag 这里称作 tailFlag, 为了概念上区别 tail, 更多强调其"哨兵"性质.
         * @return
         */
        private LinkNode func(LinkNode head, LinkNode tailFlag) {
            // 单个节点时, 退出递归
            if (head.next == tailFlag) {
                // !! 子链砍下来, 独立出来 !!
                head.next = null;
                return head;
            }
            // 取mid
            LinkNode mid = head;
            LinkNode fast = head;
            while (fast != tailFlag) {
                mid = mid.next;
                fast = fast.next == tailFlag ? tailFlag : fast.next.next;
            }

            LinkNode h1 = func(head, mid);
            LinkNode h2 = func(mid, tailFlag);
            // 归并
            return merge(h1, h2);
        }

        private LinkNode merge(LinkNode h1, LinkNode h2) {
            LinkNode dumyHead = new LinkNode(-1);
            LinkNode tail = dumyHead;
            while (h1 != null && h2 != null) {
                if (h1.value <=h2.value) {
                    tail = tail.next = h1;
                    h1 = h1.next;
                } else {
                    tail = tail.next = h2;
                    h2 = h2.next;
                }
            }

            tail.next = h1 != null ? h1 : h2;
            return dumyHead.next;
        }


    }

    /**
     * 方法二：自底向上归并排序
     * https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
     *
     * 逻辑稍麻烦些
     */
    class Solution_LC_2 {
        public LinkNode sortList(LinkNode head) {
            return null;
        }
    }


    /**
     * 自己憋的
     * 1) 如何优雅的实现"二分".
     * 2) 如何避免循环.
     */
    class Solution {
        public LinkNode sortList(LinkNode head) {
            if (head==null) {
                return null;
            }

            return func(head, null);
        }

        private LinkNode func(LinkNode head, LinkNode tail) {
            // 上来就将当前局部链砍下来 --> 在单个节点时, 砍就可以了, 这样上层末尾自然就都是断了.
            if(tail !=null) tail.next = null;
            if (head.next == null) {
                // 单个节点
                return head;
            }

            /*
            * 二分左右均匀
            * */
            LinkNode mid = getMid2(head);

            // head link1, mid link2
            LinkNode h2 = mid.next; // h1递归里会砍掉 next
            LinkNode h1 = func(head, mid);
            h2 = func(h2, tail);
            // 归并
            return merge(h1, h2);
        }

        // 注意: h1 tail guard == h2 , h2 tail guard == h2tailGuard
        // h2tailGuard 上一层的 tail guard
        private LinkNode merge(LinkNode h1, LinkNode h2) {
            LinkNode dummyHead = new LinkNode();
            LinkNode tail = dummyHead;
            while (h1 != null && h2 != null) {
                if (h1.value <=h2.value) {
                    tail.next = h1;
                    h1 = h1.next;
                } else {
                    tail.next = h2;
                    h2 = h2.next;
                }
                tail = tail.next;
            }
            if (h1!=null) {
                tail.next = h1;
            } else {
                tail.next = h2;
            }

            return dummyHead.next;
        }

        // 借助 dummy 节点, 慢1ms
        private LinkNode getMid1(LinkNode head) {
            LinkNode dummyHead = new LinkNode(-1, head);
            LinkNode mid = dummyHead;
            LinkNode fast = dummyHead.next;
            while (fast != null) {
                mid = mid.next;
                fast = fast.next != null ? fast.next.next : null;
            }
            return mid;
        }

        // fast 提前跑两位, 推荐, 逻辑简单
        private LinkNode getMid2(LinkNode head) {
            LinkNode mid = head;
            LinkNode fast = head.next != null ? head.next.next : null;
            while (fast != null) {
                mid = mid.next;
                fast = fast.next != null ? fast.next.next : null;
            }
            return mid;
        }
    }

}
